/**
 * 面试题10-2：青蛙跳台阶问题
 */
public class Offer_10_II {
    /**
     * 动态规划-空间优化
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public int numWays(int n) {
        int a = 1, b = 1, sum = 0;
        for (int i = 0; i < n; i++) {
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }

    /**
     * 动态规划
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public int numWays1(int n) {
        if (n < 2) {
            return 1;
        }
        // dp[i] 表示跳到第 n 级台阶的方案数
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Offer_10_II solution = new Offer_10_II();
        int ans = solution.numWays(7);
        System.out.println(ans);
    }
}
